Online Lectures on Bioinformatics

navigation

Algorithms for SP-optimal multiple alignments

Divide-and-Conquer Alignment

Divide and Conquer alignment jest szybkim, heurystycznym algorytmem dla wielokrotnego dopasowania sekwencji, który zapewnia optymalne wyniki dla dostatecznie homologicznych sekwencji.

Głównš ideš jest po pierwsze: nacięcie sekwencji kilka razy w niektórych punktach, aby ograniczyć długoć sekwencji, po drugie: wyrównanie naciętych sekwencji, po trzecie: powišzanie wielokrotnych dopasowań:

Problemem jest znalezienie miejsca cięcia:

i)

a) optymalne cięcie miejsca, które wytwarza optymalne alignmenty

ii)

b) zminimalizować C-optymalne cięcie miejsca

$\begin{displaymath}C(c_1,c_2,\ldots,c_n) = \sum_{l<k}C^{k,l}(c_k,c_l) \end{displaymath}$

Gdzie C jest zmodyfikowanš forward-backward-matrix:

C_ij^k,l = S^opt(s^(k),s^(l)) - (D_ij^k,l + R_ij^k,l)

Metoda ta wymaga czasu w $\mathcal{O}(L^{k-1})$ i miejsca w $\mathcal{O}(L^2n^2)$ . Podczas gdy czas ronie wykładniczo w liczbie sekwencji, miejsce jest redukowane do kwadratu. $C(c_1,c_2,\ldots,c_n)$ $\mathcal{O}(L^2n^2)$

exercises

Comments are very welcome.
luz@molgen.mpg.de